package site.wanjiahao.sort.compare;

import site.wanjiahao.sort.Sort;

public class MergeSort<E extends Comparable<E>> extends Sort<E> {

    private E[] eles;
    /**
     *      归并排序特点
     *              将一个无序序列分为两组，然后继续分为两组，直到分到一个元素为止
     *              然后将元素合并，合并成有序序列，直到合并元素为原来无序序列的元素一样为止
     */
    @Override
    protected void sort() {
        eles = (E[]) new Comparable[array.length >> 1];
        sort(0, array.length);
    }

    private void sort(int begin, int end) {
        // 数组中只有一个元素
        if (end - begin < 2) return;
        int mid = begin + end >> 1;
        sort(begin, mid);
        sort(mid, end);
        // 合并元素
        merge(begin, mid, end);
    }

    private void merge(int begin, int mid, int end) {
        int len = mid - begin;
        System.arraycopy(array, begin, eles, 0, len);
        int li = 0;
        int le = mid - begin;
        int ri = mid;
        int re = end;
        int ai = begin;
        while (li < le) {
            if (ri < re && cmp(array[ri], eles[li]) < 0) {
                array[ai++] = array[ri++];
            } else {
                array[ai++] = eles[li++];
            }
        }
    }
}
